package connect5.ia;

/*
 * Si vous utilisez Java, vous devez modifier ce fichier-ci.
 *
 * Vous pouvez ajouter d'autres classes sous le package connect5.ia.
 * 
 *
 * Vincent B�langer    (09 118 867)
 * Marc-Andr� Perrault (09 077 660)
 */

import connect5.Grille;
import connect5.Joueur;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.Vector;

/**
 *
 * @author Vincent B�langer 09118867
 * @author Marc-Andr� Perrault 09077660
 */

public class JoueurArtificiel implements Joueur {

    private int Min = Integer.MIN_VALUE;
    private int Max = Integer.MAX_VALUE;
    private double limiteTemps; 
    private boolean resteTemps;
    private double tempsPourAuCalcul = 0.65;
    public static final byte VALUE_0 = 0;
    public static final byte VALUE_N = 1;
    public static final byte VALUE_B = 2;
    private BufferedWriter LogFile;
    private byte currentPlayer;
    private byte opposent;
    private boolean DEBUG_ENABLED = false;
    
    private class ValuedPosition implements Comparable<ValuedPosition>{
    	public int[] position = new int[2];
    	public Integer value = 0;

		@Override
		public int compareTo(ValuedPosition o) {
			return value.compareTo(o.value);
		}
    }
    
    private class TreeNode{
    	public ValuedPosition valuedPosition;
    	public Vector<TreeNode> childs;
    	public TreeNode parent;
    	public Grille g;
    	public TreeSet<ValuedPosition> childsOrder;
    	
    	
    	TreeNode(int[] position, Grille g){
    		valuedPosition = new ValuedPosition();
    		if(position != null){
    			valuedPosition.position = position;
    		}
    		this.g = g;
    		childsOrder = new TreeSet<ValuedPosition>();
    	}
    	
        void maxValue(int alpha, int beta, int profondeur){
        	if(!resteTemps){
        		return;
        	}
    		childsOrder.clear();
        	if(childs == null){
        		childs = new Vector<TreeNode>();
        		for ( int[] a : Successor()){
        			//TreeNode child = new TreeNode(a, g.clone());
        			TreeNode child = new TreeNode(a, g);
        			//child.g.set(a[0], a[1], currentPlayer);
        			child.parent = this;
        			childs.add(child);
        		}
        	}
        	if(terminalState(profondeur)){
        		if(resteTemps)
        			valuedPosition.value = ValidGrille.determineValeurGrille(g, valuedPosition.position, currentPlayer);
        		if(parent != null)
        			parent.childsOrder.add(valuedPosition);
        		return;
        	}
        	else
        	{
	    		for ( TreeNode child : childs){
	    			child.g.set(child.valuedPosition.position[0], child.valuedPosition.position[1], currentPlayer);
	    			child.minValue(alpha, beta, profondeur -1);
	    			child.g.set(child.valuedPosition.position[0], child.valuedPosition.position[1], VALUE_0);
	    			if(childsOrder.last().value >= beta){
	    				valuedPosition.value = childsOrder.last().value;
	    				if(parent != null)
	    					parent.childsOrder.add(valuedPosition);
	    				return;
	    			}
	    			alpha = java.lang.Math.max(alpha, childsOrder.last().value);
	    		}
	    		valuedPosition.value = childsOrder.last().value;
	    		if(parent != null)
	    		{
	    			parent.childsOrder.add(valuedPosition);
	    		}
	        	return;
        	}
        }
        
        void minValue(int alpha, int beta, int profondeur){
        	if(!resteTemps){
        		parent.childsOrder.add(valuedPosition);
        		return;
        	}
    		childsOrder.clear();
    		if(childs == null){
        		childs = new Vector<TreeNode>();
        		for ( int[] a : Successor()){
        			//TreeNode child = new TreeNode(a, g.clone());
        			TreeNode child = new TreeNode(a, g);
        			//child.g.set(a[0], a[1], opposent);
        			child.parent = this;
        			childs.add(child);
        		}
        	}
    		if(terminalState(profondeur)){
    			if(resteTemps)
        			valuedPosition.value = ValidGrille.determineValeurGrille(g, valuedPosition.position, currentPlayer);
        		parent.childsOrder.add(valuedPosition);
        		return;
        	}
        	else
        	{
        		for ( TreeNode child : childs){
	    			child.g.set(child.valuedPosition.position[0], child.valuedPosition.position[1], opposent);
	    			child.maxValue(alpha, beta, profondeur - 1);
	    			child.g.set(child.valuedPosition.position[0], child.valuedPosition.position[1], VALUE_0);
	    			if(childsOrder.first().value <= alpha){
	    				valuedPosition.value = childsOrder.first().value;
	    				parent.childsOrder.add(valuedPosition);
	    				return;
	    			}
	    			beta = java.lang.Math.max(beta, childsOrder.first().value);
	    		}
				valuedPosition.value = childsOrder.first().value;
	    		if(parent != null)
	    		{
	    			parent.childsOrder.add(valuedPosition);
	    		}
	        	return;
        	}
        }
        
        private Vector<int[]> Successor(){
    		Vector<int[]> returnVector = new Vector<int[]>();
    		for(int x= 0; x < g.getData().length; x++)
    		{
    			for(int y =0; y < g.getData()[x].length; y++)
    			{
    				if(g.getData()[x][y] == VALUE_0)
    				{
    					returnVector.add(new int[]{x,y});
    				}
    			}
    		}
    		return returnVector;
    	}

    	private boolean terminalState (int profondeur){
    		if(tempsCourant() > limiteTemps && parent != null){
    			resteTemps = false;
    			return true;
    		}
    		
    		if (profondeur > 0 && ValidGrille.determineGagnant(g) == VALUE_0 && !childs.isEmpty()){
    			return false;
    		}
    		return true;
    	}
    	
    	void DebugPrint(int profondeur) throws IOException{
    		if(DEBUG_ENABLED){
	    		LogFile.write("Profondeur : " + profondeur +".\n");
	    		LogFile.write(g.toString()+"\n");
	    		if(childs != null){
					LogFile.write("Have childs in those position and value"+"\n");
					for ( TreeNode child : childs){
						LogFile.write("X : " + child.valuedPosition.position[1] + " Y : " + child.valuedPosition.position[0] + " Value : " + child.valuedPosition.value+"\n");  
		    		}
	    		}
				if(!childsOrder.isEmpty()){
	    			LogFile.write("Maximum child value : X : " + childsOrder.last().position[1] + " Y : " + childsOrder.last().position[0] + " Value : " + childsOrder.last().value+"\n");
	    			LogFile.write("Minimum child value : X : " + childsOrder.first().position[1] + " Y : " + childsOrder.first().position[0] + " Value : " + childsOrder.first().value+"\n");
	    		}
	    		LogFile.write("Current value : X : " + valuedPosition.position[1] + " Y : " + valuedPosition.position[0] + " Value : " + valuedPosition.value+"\n");
	    		if(childs != null && profondeur > 0){
	    			LogFile.write("Childs Debug Value : "+"\n");
	    			LogFile.flush();
	    			for ( TreeNode child : childs){
	    				child.g.set(child.valuedPosition.position[1], child.valuedPosition.position[0], (profondeur % 2 == 1)?currentPlayer : opposent);
	    				child.DebugPrint(profondeur-1);
	    				child.g.set(child.valuedPosition.position[1], child.valuedPosition.position[0], VALUE_0);
	    			}
	    		}
    		}
    	}
    }

    @Override
    public int[] getProchainCoup(Grille g, int delais) { 
    	try {
    		if(DEBUG_ENABLED)
    			LogFile = new BufferedWriter(new FileWriter("LogFile.txt", false));
    		
			currentPlayer = ( (g.nbLibre()%2 == 1 && g.getData().length%2 == 1 && g.getData()[0].length%2 == 1) || //La longueur des cotés sont deux nombres impaire ainsi que le nombre de case restante
							  (g.nbLibre()%2 == 0 && (g.getData().length%2 == 0 || g.getData()[0].length%2 == 0))  )? //Le nombre de case restante est pair ainsi que l'un (au minimum) des cotés
									  VALUE_N :
										  VALUE_B;
			opposent = (byte) ((currentPlayer%2) +1);
			TreeNode root = new TreeNode(null,g);
	        root.g = g;
	        root.parent = null;
	    	resteTemps = false;
	        limiteTemps = tempsCourant() + delais * tempsPourAuCalcul; 	// Convertir de miliseconde � l'unit� du temps courant
	        int maxprofondeur = 1; 				// On commence avec une profondeur de 1 (peut-�tre commenc� � 2)
	        int[] solution = new int[]{0, 0}; 	// Coordonn� (x , y)
	        while(tempsCourant() < limiteTemps){
	           int[] nouvellesolution = alphaBeta( Min, Max , maxprofondeur,root);
	           if(resteTemps) 
	        	   solution = nouvellesolution;
	          maxprofondeur++;
	        }
	        
	        if(DEBUG_ENABLED)
	        	LogFile.close();
	        System.out.println("Derniere profondeur complete : " + (-- maxprofondeur));
	        return solution;
		} catch (IOException e) {
			e.printStackTrace();
		}
        return null;
    }

    private int[] alphaBeta( int alpha, int beta, int profondeur,TreeNode root) throws IOException{
    	if( tempsCourant() >= limiteTemps){
    		resteTemps = false;
    		return null;
        }
        resteTemps = true;
        
        root.maxValue(alpha, beta,profondeur);
        
        if(DEBUG_ENABLED){
	        LogFile.write("------------------------------------------------------------------"+"\n");
	    	root.DebugPrint(profondeur);
        }
    	
        return root.childsOrder.last().position;
    }

	private double tempsCourant(){
		return System.currentTimeMillis();
	}
	
}
